package top.ivansong92.example.leetcode.learning.data.struct.queue;


import org.junit.Test;

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;

public class TestExample {
    /**
     * 102. 二叉树的层序遍历
     */
    /**
     * Definition for a binary tree node.
     */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return Collections.emptyList();
        }

        List<List<Integer>> res = new ArrayList<>();
        LinkedList<TreeNodeWithLevel> queue = new LinkedList<>();
        queue.addLast(new TreeNodeWithLevel(root, 0));

        while (!queue.isEmpty()) {
            TreeNodeWithLevel val = queue.removeFirst();
            if (val.level >= res.size()) {
                res.add(new ArrayList<>());
            }

            TreeNode node = val.node;
            res.get(val.level).add(node.val);
            if (node.left != null) {
                queue.addLast(new TreeNodeWithLevel(node.left, val.level + 1));
            }

            if (node.right != null) {
                queue.addLast(new TreeNodeWithLevel(node.right, val.level + 1));
            }
        }
        return res;
    }

    private static class TreeNodeWithLevel {
        TreeNode node;
        int level;
        public TreeNodeWithLevel(TreeNode node, int level) {
            this.level = level;
            this.node = node;
        }
    }


    /**
     * 107. 二叉树的层序遍历 II
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if (root == null) {
            return Collections.emptyList();
        }

        List<List<Integer>> list = new ArrayList<>();
        LinkedList<TreeNodeWithLevel> queue = new LinkedList<>();
        queue.addLast(new TreeNodeWithLevel(root, 0));

        while (!queue.isEmpty()) {
            TreeNodeWithLevel val = queue.removeFirst();
            if (val.level >= list.size()) {
                list.add(new ArrayList<>());
            }

            TreeNode node = val.node;
            list.get(val.level).add(node.val);
            if (node.left != null) {
                queue.addLast(new TreeNodeWithLevel(node.left, val.level + 1));
            }

            if (node.right != null) {
                queue.addLast(new TreeNodeWithLevel(node.right, val.level + 1));
            }
        }
        List<List<Integer>> res = new ArrayList<>();
        for (int i = list.size() - 1; i >= 0; i--) {
            res.add(list.get(i));
        }
        return res;
    }

    /**
     * 103. 二叉树的锯齿形层序遍历
     * @param root
     * @return
     */
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if (root == null) {
            return Collections.emptyList();
        }


        List<List<Integer>> list = new ArrayList<>();
        LinkedList<TreeNodeWithLevel> queue = new LinkedList<>();
        queue.addLast(new TreeNodeWithLevel(root, 0));

        while (!queue.isEmpty()) {
            TreeNodeWithLevel val = queue.removeFirst();
            if (val.level >= list.size()) {
                list.add(new ArrayList<>());
            }

            TreeNode node = val.node;
            if (val.level % 2 == 0) {
                list.get(val.level).add(node.val);
            } else {
                list.get(val.level).add(0, node.val);
            }

            if (node.left != null) {
                queue.addLast(new TreeNodeWithLevel(node.left, val.level + 1));
            }

            if (node.right != null) {
                queue.addLast(new TreeNodeWithLevel(node.right, val.level + 1));
            }
        }

        return list;
    }


    @Test
    public void testMinSubArrayLen() {
        System.out.println(numSquares(12));
    }

    /**
     * 279. 完全平方数
     * @param n
     * @return
     */
    public int numSquares(int n) {
        if (n <= 1) {
            return 1;
        }
        LinkedList<Node> queue = new LinkedList<>();
        queue.addLast(new Node(n, 0));
        boolean[] visited = new boolean[n + 1];
        while (!queue.isEmpty()) {
            Node node = queue.removeFirst();
            int level = node.level;
            int val = node.val;
            visited[val] = true;
            for (int i = 1; ; i++) {
                int plus = val - i * i;
                if (plus < 0) {
                    break;
                }

                if (plus == 0) {
                    return level + 1;
                }

                if (visited[plus]) {
                    continue;
                }

                queue.addLast(new Node(plus, level + 1));

            }
        }

        return 0;
    }

    private static class Node {
        int val;
        int level;
        public Node(int val, int level) {
            this.level = level;
            this.val = val;
        }
    }

    /**
     * 300. 最长递增子序列
     * @param nums
     * @return
     */
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int len = nums.length;
        if (len == 1) {
            return 1;
        }

        LinkedList<SeqNode> queue = new LinkedList<>();
        for(int i = 0; i < len; i ++) {
            queue.addLast(new SeqNode(nums[i], 1, i));
        }

        int max = 1;
        SeqNode node;
        while (!queue.isEmpty()) {
            node = queue.removeFirst();
            if (node.level == -1) {
                continue;
            }
            max = Math.max(node.level, max);
            if (max == len) {
                return len;
            }

            int nextVal = node.level + 1;
            int val = node.val;
            for (int i = node.index + 1; i < len; i++) {
                if (nums[i] > val) {
                    queue.addLast(new SeqNode(nums[i], nextVal, i));
                }
            }
        }
        return max;
    }

    private static class SeqNode {
        int val;
        int level;
        int index;
        public SeqNode(int val, int level, int index) {
            this.level = level;
            this.val = val;
            this.index = index;
        }
    }


    @Test
    public void testLadderLength() {
        System.out.println(ladderLength("hit", "cog", Arrays.asList("hot","dot","dog","lot","log","cog")));
    }

    /**
     * 127. 单词接龙
     * @param beginWord
     * @param endWord
     * @param wordList
     * @return
     */
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (wordList == null || wordList.size() == 0) {
            return 0;
        }
        int len = wordList.size();
        boolean[] visited = new boolean[len];

        boolean matchEnd = false;

        LinkedList<LadderNode> queue = new LinkedList<>();

        for (int i = 0; i < len; i++) {
            String word = wordList.get(i);
            if (changeOneChar(word, beginWord)) {
                queue.addLast(new LadderNode(word, 1, i));
                visited[i] = true;
            }

            if (word.equals(endWord)) {
                matchEnd = true;
            }
        }

        if (!matchEnd) {
            return 0;
        }

        while (!queue.isEmpty()) {
            LadderNode node = queue.removeFirst();
            String val = node.val;
            int nextLevel = node.level + 1;
            if (val.equals(endWord)) {
                return node.level + 1;
            }

            for (int i = 0; i < len; i++) {
                if (visited[i]) {
                    continue;
                }

                String word = wordList.get(i);
                if (changeOneChar(word, val)) {
                    queue.addLast(new LadderNode(word, nextLevel, i));
                    visited[i] = true;
                }
            }
        }

        return 0;
    }

    private static class LadderNode {
        String val;
        int level;
        int index;
        public LadderNode(String val, int level, int index) {
            this.level = level;
            this.val = val;
            this.index = index;
        }
    }

    @Test
    public void testFindLadders() {
        System.out.println(findLadders("hit", "cog", Arrays.asList("hot","dot","dog","lot","log")).size());
    }
    /**
     * 126. 单词接龙 II
     * @param beginWord
     * @param endWord
     * @param wordList
     * @return
     */
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        int len = wordList.size();

        boolean matchEnd = false;

        LinkedList<LadderNodeV2> queue = new LinkedList<>();

        LadderNodeV2 root = new LadderNodeV2(beginWord, null, 0);
        for (int i = 0; i < len; i++) {
            String word = wordList.get(i);
            if (changeOneChar(word, beginWord)) {
                queue.addLast(new LadderNodeV2(word, root, 1));
            }

            if (word.equals(endWord)) {
                matchEnd = true;
            }
        }

        if (!matchEnd) {
            return Collections.emptyList();
        }


        List<LadderNodeV2> matchNodeList = new ArrayList<>();
        Integer depth = null;
        while (!queue.isEmpty()) {
            LadderNodeV2 node = queue.removeFirst();
            String val = node.val;
            if (val.equals(endWord)) {
                if (depth == null) {
                    depth = node.depth;
                }

                if (node.depth > depth) {
                    continue;
                }

                matchNodeList.add(node);
                continue;
            }

            int newDepth = node.depth + 1;
            if (depth != null && newDepth > depth) {
                continue;
            }

            if (newDepth > wordList.size()) {
                break;
            }

            for (int i = 0; i < len; i++) {
                String word = wordList.get(i);
                if (changeOneChar(word, val)) {
                    queue.addLast(new LadderNodeV2(word, node, newDepth));
                }
            }
        }

        if (matchNodeList.size() == 0) {
            return Collections.emptyList();
        }

        List<List<String>> res = new ArrayList<>();
        for (LadderNodeV2 node : matchNodeList) {
            List<String> list = new ArrayList<>();
            LadderNodeV2 index = node;
            while (index != null) {
                list.add(0, index.val);
                index = index.parent;
            }
            res.add(list);
        }

        return res;
    }

    private boolean changeOneChar(String word1, String word2) {
        if (word1.length() != word2.length()) {
            return false;
        }

        int len = word1.length();
        int counter = 0;
        int i = 0, j = len - 1;
        while (i <= j) {
            char ch1 = word1.charAt(i);
            char ch2 = word2.charAt(i);
            if (ch1 != ch2) {
                counter ++;
            }

            if (i != j) {
                ch1 = word1.charAt(j);
                ch2 = word2.charAt(j);
                if (ch1 != ch2) {
                    counter ++;
                }
            }
            if (counter > 1) {
                return false;
            }

            i ++;
            j --;
        }
        return counter == 1;
    }


    private static class LadderNodeV2 {
        String val;
        LadderNodeV2 parent;
        int depth;
        public LadderNodeV2(String val, LadderNodeV2 parent, int depth) {
            this.parent = parent;
            this.val = val;
            this.depth = depth;
        }
    }

    @Test
    public void testTopKFrequent() {
        System.out.println(Arrays.toString(topKFrequent(new int[]{1,1,1,2,2,3}, 2)));
    }

    /**
     * 347. 前 K 个高频元素
     * @param nums
     * @param k
     * @return
     */
    public int[] topKFrequent(int[] nums, int k) {
        if (nums == null || nums.length <= 1 || k <= 0) {
            return nums;
        }

        Map<Integer, AtomicInteger> counterMap = new HashMap<>();
        for (int n : nums) {
            AtomicInteger counter = counterMap.computeIfAbsent(n, e -> new AtomicInteger(0));
            counter.incrementAndGet();
        }

        PriorityQueue<KNode> queue = new PriorityQueue<>(k);
        for (Map.Entry<Integer, AtomicInteger> entry : counterMap.entrySet()) {
            if (queue.size() >= k) {
                int counter = entry.getValue().get();
                KNode kNode = queue.peek();
                if (kNode.counter >= counter) {
                    continue;
                }
                queue.poll();
            }
            queue.add(new KNode(entry.getKey(), entry.getValue().get()));
        }

        int[] res = new int[k];
        int index = 0;
        for (KNode node : queue) {
            res[index++] = node.val;
        }
        return res;
    }

    private static class KNode implements Comparable<KNode> {
        int val;
        int counter;

        public KNode(int val, int counter) {
            this.val = val;
            this.counter = counter;
        }

        @Override
        public int compareTo(KNode o) {
            return this.counter - o.counter;
        }
    }
}
